Fiery Redemption, Frozen Rebirth
by Ichko
Summary: As an unlikely due end up in a land not their own, what will they do to survive and how will they change along the way?
1. Chapter 1

**Fiery Redemption, Frozen Rebirth chapter 1**

**I do not own the Lord of the Rings or A song of Ice and Fire.**

* * *

Arya slowly opened her silver eyes, the surrounding world remaining but a blur to her yet.

From what she could make out, she was in a forest, but not like the Wolfwoods, a dark bleak place. No, instead, the forest was warm and sunny, golden rays streaming through the treetops. As her eyesight began to clear up, Arya saw Nymeria standing but a meter away, sitting on her hind legs and staring at something beneath the petite girl.

Casting her gaze down, Arya saw a beautiful woman with scarlet hair and a dress to match, a choker with a red crystal around her neck. Even with lying on the ground among all the leaves, she remained stunningly beautiful. As the outlandish woman began waking up, Arya swiftly got off of her, scrambling to her feet and dusting her simple grey dress.

With a heavy groan, the red-head rose to a sitting position, clutching her head with one hand before her eyes snapped open, crimson meeting silver.

The two stared at one another for a long time before Arya helped the woman up and retreating a few steps away, Nymeria coming to stand behind her, not menacingly, yet the wolf's eyes remaining focused on the red-clad woman.

"You have a beautiful dog, girl." Said the woman, smiling gently.

"Nymeria is not a dog! She is a direwolf!" responded Arya, a glare finding its way to her face.

"My apologies, Nymeria. And what would be your name, little girl, to keep a direwolf as a pet?"

"Arya Stark." Answered uncertainly the petite girl.

"Stark?" mumbled the older woman. "Am I in Westeros, then?"

"Yes! No… maybe? I don't know… I was playing by the river with Mycah…and then Joffrey came with Sansa… and he to attack Mycah, then I hit him with a stick… and he tried to run me through with his sword!" Arya nearly shouted out the last part.

The strange woman simply rose an elegant eyebrow at the statement, not really understanding everything that she was saying.

"And then I slipped on mud around the shore and fell in the rive-" Arya cut herself short, suddenly beginning to clutch at her clothes.

"I am dry!" she said, her grey eyes wide.

"And then what happened, Arya Stark?" asked the woman, no longer smiling.

"I… I don't know. I woke up here, lying on you."

"Interesting…" mumbled the woman, taking a look around, for there was no river nearby, nor any armed men that might guard a prince and whoever else Arya Stark would have traveled with.

"My name is Melisandre of Asshai, little Arya." The petite girl's eyes widened, her mouth gaping.

"You are from the free cities?!" nearly shouted the young Stark, her excitement seeping through.

A smile forming on her face, Melisandre took a step forth and put a hand on Arya's shoulder.

"Come one. We are on a road. And roads lead to villages." She said, gently nudging her in the direction she was facing.

As they both turned to make way down the leaf-covered road, a group of men suddenly fell from the cliff to their right, piling right infront of them.

"Uh, that was close." Said one of the men that was at the bottom of the pile, his face but a hand away from a large pile of droppings, while another complain about breaking a bone… only to pull a broke carrot from beneath him.

"Trust a Brandybuck and a Took!" said an angry voice, the chubby man rising and beginning to dust himself off.

"What? It was a detour! A shortcut!" said the one next to him.

"A shortcut to what?" asked the angry one.

"The mushrooms!" shouted the first in a happy voice.

He and the angry one then rushed forth to gather said mushrooms, not noticing the trio. That is, until they came right infront of them.

With the men been so close, the two woman and wolf noticed that they were rather…short. To add to that, they all had large hairy feet with no shoes on.

"Oh, uhh, miladies." Said the first, trying to bow, only to back away slowly seeing Nymeria coming from around the two of them. Seeing this, Arya scowled at the wolf.

"Nymeria, sit."

The wolf obediently sat, defusing the situation while Melisandre stepped forth.

"Good day, gentlemen. Would you mind telling us where we are?"

"Why, most certainly, milad- Pippin, the mushrooms!" and indeed, the angry one has by now collected a good half of the mushrooms while the one infront of them is yet to start.

"You, my ladies, are near the border of the Shire! This road leads to it while this way " he said, pointing behind them " leads to Bree."

"And where would this Shire be located?" pressed on the red-clad lady, her smile falling from her face while Arya had nothing but confusion on her features. As the one that conversed with them began to uncertainly scratch his curly-haired head, the last one that has yet to utter a thing spoke.

"Middle Earth" he said, yet his voice lowered towards the end before moving past the two ladies and wolf, a worried expression on his face. Melisandre felt it too, an approaching presence, so dark that no flame could cast a light on it.

"I think we should get off the road." He said, looking back at his friends

Nymeria started to growl, barely audible at first, while the strange man once again looked towards the end of the road. As a strange wind began blowing leaves away, Melisandre began pushing Arya off the road, her eyes fixed on the forest path.

"Get off the road! Quick!" shouted the small man, his friends that had ignored him so far snapping into action.

They all jumped of the path, taking cover beneath a tree root. They all stood there, all parties scared at the behaviours of their respective companions. Melisandre had her eyes closed, clutching her hands to her chest as if preying while Arya stood, looking between her and Nymaria, who had her eyes to her head, seemingly afraid.

"What is-"she began, only for the man to hiss.

"Quiet." Just as he said that, the sound of horsehooves appeared above them before the clincking of plate boots on the forest floor filled the air.

Arya saw an armored hand grasping the root she was hiding beneath, a sniffing sound resonating around. Suddenly becoming hiper aware at her surroundings and the hundreds of bugs and insects crawling all around, Arya was glad for someone throwing a bag to the side and the rider leaving their place in a loud screech that made her jump.

They quickly broke cover and all of them begam running for the thick vegetation further down the slope. A good distance away, they all stopped to catch their breath.

"What was that?" asked one of the short barefeet men, yet no one dared to answer him.

All of them getting their bearing back, eyes once again found their way to the opposing parties.

"So… I am Meriadoc Brandybuck, the idiot over there is Peregrin Took. The no-fun snob is Samwise Gamgee and he is Frodo Baggins. But you can call me Merry."

"I am Melisandre of Asshai while this is Arya Stark" Melisandre saw no recognition of the name Stark in the eyes of the men infront of her which further fueled her suspicions. Be it small folk or lesser lords, people should know the great lords of the surrounding lands "And this is-"

"Nymeria." Said Arya, putting her hands around the wolf's neck.

"Asshai, milady? Is this somewhere in the realm of man?" asked Samwise.

"The realm of man?" asked Melisandre.

"We should get moving." Said the now named Frodo, breaking the relaxed atmosphere that had begun to settle just before a screech tore through the silent forest. The group continued down the hill, running from tree to tree and they continued so until darkness fell.

Stopping once more, Merry approached Frodo, asking.

"That black rider was looking for something, or someone…?" Frodo met his gaze before tearing his eyes away. A sudden growl from Nymeria and they all ducked for cover as a dark figure appeared on the horizon, the illumination of the moon behind him.

"I have to leave the Shire. Me and Sam must get to Bree." Said Frodo.

"Bree is a town?" asked Arya.

"Yes. Follow me! Uncle Berry's ferry!" said Merry breaking into a run as the figure on the hilltop disappeared.

As the group ran, the same black rider suddenly appeared through the trees, creating panic as the group was split in two. As Melisandre came face to face with the shade, she was stunned. As a shadowbinder, she had knowledge and experience, yet this, it felt so much sinister than anything she has laid her eyes on. With the red priestess unable to conjure flames, only control them, she was completely powerless in the darkness of the woods.

Somehow, the group managed to get away from the rider, jumping over a fence, which was quite a nuecence for the two ladies clad in dresses. They eventually made it to a barge on a river and all of them rushed to get on.

"Cut the ropes, Sam!" yet as the roped were disentangled, Frodo just appeared out of the woods, the shadow quickly gaining distance behind him.

With the ferry already separated from the dock, Frodo had to jump just to get on, the rider coming to a screeching halt, the group finally able to get a good look at him.

"How far is the nearest crossing?" asked the out of breath Frodo.

"Brandywine bridge, 20 miles." Responded Merry.

As they began heading down the river, they suddenly saw another two riders joining the one from the dock, all three of them entering the forest and out of sight.

* * *

It has started raining some time ago, the small men been kind enough to give some of their cloacks to the ladies to cover their heads from the rain. After leaving the ferry, they quickly made their way to the wooden gates of a small town, an old gatekeeper with a lanther meeting them.

He was surprised at the strange company, calling the small men 'hobbits', yet letting them through nonetheless.

Entering the town, at first it did not look so bad from afar, some might have even called it homely. Yet as they went ever deeper along the muddy streets which became ever tighter, a rougher and rougher crowed began appearing around them, Melisandre whispering to Arya to pull the hood tighter around her head, Nymeria moving closer to her mistress and baring her teeth and anyone that came too close.

Eventually finding the inn that the hobbits were looking for, quickly entering inside. The bartender was courteous, even if he was, in the end, simply trying to sell them rooms for the night. Arya made a move to remove the hood as the hobbits did so, yet her companion quickly stopping her from doing so. The petite girl could see that she was looking across the inn from beneath the rim of her hood.

"Ah, yes. Elderly fellow. Big grey beard, pointy hat!" said the bartender "Haven't seen him in six months." He finished, shaking his head.

The group, suddenly finding itself without a direction, found themselves a table at the end of the room, yet nevertheless gathering a lot of looks. A group of two women, a large dog and four hobbits was something unique by any standarts.

While the Hobbits were sitting at their end of the table, uncertain and drinking, Melisandre had asked for the largest map from the people around. It gathered many strange looks, but few could refuse a beautiful woman and she did pay them a gold coin, even if it was not one from around here. Gold is gold.

Stretching the map on their end of the table, both of them sullenly looked over it, trying to find anything they could recognize. Melisandre knew Essos well, the area around Asshai in great detail at that, while Arya, with her obsession over castles and combat in general, knew the shape of Westeros and where most of the major fortresses were located.

Grey havens, Minas Tirith, Erebor, Isengard… nothing familiar. Arya began shaking slowly when they finally found where Bree was, absolutely nothing that either of them knew around it.

"W-what does that mean?" asked slowly Arya, lifting her silver eyes to meet Melisandre's red ones. Eyes filled with as much doubt and concern as hers.

"It means… we are no longer home." Said Melisandre, her voice finally losing the vibe of confidence and assurance it possessed.

* * *

**I hope you like the story as it is going so far, not that we had that much to see from it yet. I have several major ideas about it. Whether to stick with a more canon approach or go with other events, like the War in the North, for example. Whether to splits the two girls is also a question etc. I have an idea about Arya that does involve a theory about the Starks' connection with the White Walkers, but for now, it will remain in the background.**

**Anyway, I hope you enjoyed, leave your thoughts in the reviews of PM me if you wish. All cryticism is welcomed.**

**Thank you for reading.**


	2. Chapter 2

**Fiery Redemption, Frozen Rebirth chapter 2**

**I do not own Lord of the Rings or A song of Ice and Fire.**

* * *

The duo stood silently, their eyes fixed at the map, yet seeing nothing. Both of them were lost in thoughts, each of their minds running a thousand thoughts a minute as they slowly began to comprehend just what was actually happening, what situation they were in. Their food stood forgotten, long cold and it took Nymeria gently nudging Arya to snap them both out of their trance.

It was a hard realization that weighted heavily on the two females. While Melisandre was used to getting through all on her own, having been ripped from her family at an early age, she was nevertheless in a completely unknown realm to her. One with different moralities, believes and above all, races. Just their companions sitting on the opposite end of the table from the two of them were a proof of that. Hobbits, they were called, from what she gathered. When she first met them, the red woman easily dismissed them as a group that had bounded together over been dwarves with strange leg deformities. And yet, there were quite a lot more of them in this town, the strangest thing of all been that none of them were discriminated or talked down to in any way.

All of them were simply… accepted.

Her companion, on the other hand, had it worse off. She was a young girl after all who had lived all her life in the comforts of a castle, surrounded by servants and here was she now, away from all that she knew.

"That fellow over there has been staring at us since we came in came in here!" said Sam in a loud voice, drawing the two females' eyes towards him.

Following the hobbits' gaze, their vision landed on a hooded man in the corner of the room, a strange smoking device in his mounts, the single candle on the table barely illuminating the bottom half of his face.

"Excuse me," began Frodo, stopping the innkeeper as he was passing by "that fellow over there. Who is he?" the old man suddenly looked uneasy, bending down and in a hushed tone that carried over the table said:

"He is one of them ranger, dangerous folk. We don't know his real name, but around here he is known as Strider." He finished, walking away to deliver the ale that he was carrying.

The group fell back into silence, Arya glaring at the man from beneath the rim of her own hood, the fact that she was not in her own temporarily forgotten.

"Frodo Baggings? I know him!" a loud voice suddenly carried over the entire inn. It was Pipin over at the bar, surrounded by a group of gruff looking men while poiting at their table. The grave silence that fell as every eye in the inn found its way to their table was broken as the hobbit on question sprang into action, quickly getting to his companion's side, trying to silence him. They got into a slight scuffle, Frodo falling on the floor, his hand extended upwards and but a second later, the hobbit disappeared, lithuraly. One second he was there, the next… gone.

Gasps filled the room, all eyes drawn to where Frodo used to be, no one daring to move. The two foreign girls different reactions to this. While Arya remained rooted to her seat, eyes wide and mount agape, Melisandre wore a calculative look on her face, the red head trying to figure out just what the hobbit had done. The priestess was well aware of the actual existence of magic, but she knew that most of what people claimed to be sorcery was actually simple, cheap illusions.

As people around the inn were slowly begging to return to their previous actions, the three hobbits began frantically looking around for their friend.

It was Nymeria that suddenly looked towards the staircase, the sharp movement causing Arya to follow the gaze of the previously calm wolf just in time to see the hooded man, Strider, hauling Frodo up the stairs towards the second floor.

"Nymeria!" before the petite girl could even reign in her wolf, the animal was already moving after the pair, silently, yet swiftly making her way across the room, Arya's shout having drawn her companions' attention towards her.

"She found Frodo! Quick!" shouted the wolf-blooded girl, grabbing the knife from her long-cold meal. All of them rushed after Arya as she bolted up the staircase, the group grabbing items along the way that might be used as weapons if one had the imagination for it.

Reaching the second floor, they found Nymeria quietly sitting in front of a door, not a tad bit of hostility present in the wolf. The hobbits, on the other hand, simply burst into the room.

"Let him go or I will have you!" shouted Sam, the man meeting them with his sword drawn while the hobbits were pointing a variety of household items, including chairs and candlestick.

Arya and Melisandre entered the room, been able to get a good look at the man as his hood no longer in place. He was perhaps in his late thirties, long dark hair framing unkempt beard with dark eyes marring his face.

"You have a stout heart, little hobbit." The man said, lessening his stance and putting his sword back into the hidden sheath. "But it will not save you."

It was Nymeria that 'broke the ice' sort to speak, coming from behind the group and gently nudging the man's hand, Strider saying something incomprehensible to all of them in a soft voice, gently scratching the wolfs' head before turning towards Frodo.

"You no longer wait for the wizard, Frodo. They are coming."

"What is coming?" asked Melisandre, the hobbits having lowered their improvised weapons seeing as the man had put his sword away.

"The same things that hunted you on your way here. We must move." He said, before picking a bag from the room, Arya quickly assuming it was his in the first place.

Somehow trusting the man, the group made its way back downstairs before exiting through the backdoor as not to draw much attention before making for a tavern across the street. Quickly finding a room there, sadly with a single bed only.

Not much was spoken between the group, yet Nymeria trusted the man and that was enough for Arya and somehow, even for Melisandre.

So they all stood silently, Merry, Pipin and Sam having fallen asleep on the bed with Frodo leaning on it. Arya stood on the ground, her legs pulled to her chest, absentmindedly stroking Nymeria's head as the wolf lay next to her. Melisandre was seated on a chair, opposite to Strider who sat on a chair as well next to the fireplace, sword leaning on his chest while looking at the wolf.

"You have a beautiful wolf, my lady."

Grey eyes snapped from the fire, meeting the ranger's eyes, wide in surprise, her previous worry once again forgotten.

"You are the first to actually realize that Nymeria is a wolf and not a dog." Said the girl in a happy voice, yet her smile slowly began declining, her gaze returning back to the fire. Seeing her sad gaze, Strider pressed on.

"What troubles you?" he asked in a soft voice.

"Home." Returned the girl just as softly, her voice barely above a whisper, a sharp contrast to the usually strong-willed girl.

Silence fell back into the room, Arya eventually unfolding the map once more and for what felt like hours, she scanned all corners of it, looking for anything remotely familiar, not noticing the sad gazes by her three still awake companions.

It was not before long that she fell asleep, her head resting onto Nymerias' soft neck. Strider scoped her up from the cold floor and laid her onto the bed close to the windows. Despite there already been three hobbits onto it, there was still enough room for the petite girl.

After returning to his seat, Melisandre finally asked the question that was on her mind since meeting the strange man.

"Why did you help us?" she asked, straight to the point, her red eyes narrowed as she looked at the man across from her.

"Gandalf send me ahead if something happened. Since he was not here, I guess it did…"

"You are a friend of Gandalf?" asked Frodo, the only hobbit still awake.

Strider turned his head towards the small man before giving a single nod.

"Aye" he responded softly.

"You are a companion of hers?" suddenly asked the ranger, turning back to Melisandre and indicating Arya with his head.

"You could say that." Responded the fiery woman.

"She mentioned home… Where is home?" pressed on the man.

"Out of our reach." Was all she said before getting up from her chair and moving towards the fire, gently stepping over Nymeria that while still was laying on the ground, remained awake, her golden eyes following the red figure as she threw a log into the dying fire.

"Forgive me, my lady. It was rude of me to ask." Said the man in a low voice, genuinely sorry, surprising the woman.

"It is alright. We are unsure of where are we exactly. Not all corners of where we come from are explored and yet" she said, spreading her left arm towards the map that still layed stretched on the ground "nothing is familiar on this map." Finished Melisandre, her voice even.

As Strider cast a look at the map himself, he saw that it was actually a map of the whole of Middle Earth, not just a small part of it, lacking any details. They all fell back into silence, Melisandre turned back to the fire and seemingly began to prey while the ranger was warily casting looks out of the window every few seconds or so.

Just as they stood in silence, only the cracking of the fire breaking it, that Nymeria suddenly growled. The man swiftly looked at the wolf that was now on its feet and looking towards the window, that somehow prompting him to put out the last candle still alit in the room, leaving only the dying fire for gentle illumination.

The thundering sound of horse hooves filled the room, coming from the street below as five dark-clad riders quickly dismounted and entered their previous inn. Tense moments turned into minutes which felt like hours, Melisandre noticing that Strider tightened his grip on his sword, yet remaining as still as possible while she herself moved between the fire and the window, hiding what little illumination there still was.

Arya had awoken from the thunderous hooves, yet she rose slowly, drawing the other threes' eyes towards herself as she got up from the bed and sat in the chair that Melisandre was previously occupying. The petite girl somehow felt just how tense the situation really was and remained silent, Nymeria coming to rest her head on Arya's legs, the silver-eyed girl burring her fingers in the thick fur.

What could only be described as an unholy screech pierced the quiet night, making Arya jump and awakening the rest of the hobbits. Not before long, they were all able to see the five figures quickly exiting the inn, mounting and riding away, still screeching, awakening the entire town, only for everyone to cower in the dark corners of their homes.

"What are they?" asked Frodo, a question that was on everyone's' minds.

"They were once men. The great kings of men. Then Sauron the Deciever gave to them the nine rings of power. Blinded by their greed, they took them without question. One by one, they fell into darkness." Strider began his dark tale, looking out of the window before turning to face Frodo.

"They are the Nazgul, Ring-Wraiths. Neither living, nor dead. At all times, they feel the presence of the ring, drawn to the power of the one. They will never stop hunting you."

As shivers went up everyone's' back, Arya turned to look at the now named Nazguls' retreating backs while Melisandre turned to the fire, as if hoping to find guidance in the softly warmth and illumination it provided.

* * *

**Second chapter up. If I am to be honest, there would probably be little to no difference up to Rivendell, which would be like two chapters away at most.**

**Someone asked about Aragorn and what he is actually an heir to. Now, I have not read the books, nor am I going to pretend that I have. I am going to base this on the movies, because it is what I am familiar with and in the end of the day, it is the more easier of the two sources to go back to and get a reference if you forget some aspect of the story.**

**Anyway, I hope you guys enjoyed it, leave a review or PM me if you did, it is greatly appreciated either way.**

**Thank you for reading.**


End file.
